package com.example.algorithm.service.impl;

import com.example.algorithm.model.ListNode;
import com.example.algorithm.model.Node;
import com.example.algorithm.service.TreeService;
import org.springframework.stereotype.Service;

import com.example.algorithm.model.TreeNode;

import java.util.*;

/** 二叉树
 * @author Administrator
 * @date 2024/7/25 19:40
 * @description
 */
@Service
public class TreeServiceImpl implements TreeService {
    /**NO.36 二叉树的中序遍历
     * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
     * @param root
     * @return
     * 解法一：递归
     * 解法二：迭代
     * 解法三：Morris 中序遍历
     * 解法四：颜色标记法
     *
     */
    @Override
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty()||curr!=null){
            if(curr!=null){
                stack.push(curr);
                curr =curr.left;
            }else{
                curr = stack.pop();
                list.add(curr.val);
                curr = curr.right;
            }
        }
        return list;

    }

    /** NO.37二叉树的最大深度
     * 给定一个二叉树 root ，返回其最大深度。
     *
     * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
     * @param root
     * @return
     * 解法一：深度优先算法(DFS)
     * 解法二：广度优先算法(BFS)
     *
     *
     */
    @Override
    public int maxDepth(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int length=0;
        while (!queue.isEmpty()){
            int size=queue.size();
            while (size>0){
                TreeNode node = queue.poll();
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
                size--;
            }
            length++;
        }
        return length;

    }

    /** NO.38翻转二叉树
     * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
     * @param root
     * @return
     * 解法一：深度优先算法(DFS)
     * 解法二：广度优先算法(BFS)
     *
     *
     */
    @Override
    public TreeNode invertTree(TreeNode root) {
        if (root == null){
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size=queue.size();
            while (size>0){
                TreeNode node = queue.poll();
                TreeNode tmp = node.left;
                node.left = node.right;
                node.right = tmp;

                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
                size--;
            }
        }
        return root;
    }

    /**  NO.39对称二叉树
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     * @param root
     * @return
     * 解法一：深度优先算法(DFS)
     * 解法二：广度优先算法(BFS)
     *
     *
     */
    @Override
    public boolean isSymmetric(TreeNode root) {
        if (root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()){
                TreeNode left =queue.poll();
                TreeNode right =queue.poll();
                if(left==null&&right==null){
                    continue;
                }
                if(left==null||right==null||(left.val!=right.val)){
                    return false;
                }
                queue.offer(left.left);
                queue.offer(right.right);
                queue.offer(left.right);
                queue.offer(right.left);

            }
        return true;
    }

    /** NO.40 二叉树的直径
     * 给你一棵二叉树的根节点，返回该树的 直径 。
     *
     * 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
     *
     * 两节点之间路径的 长度 由它们之间边数表示。
     * @param root
     * @return
     *
     * 解法一：深度优先算法(DFS)
     *
     */
     private int maxPath = 0;
    @Override
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null){
            return 0;
        }
        getPath(root);
        return maxPath;
    }



    private int getPath(TreeNode root){
        if(root == null) {
            return 0;
        }
        int leftHeight = getPath(root.left);
        int rightHeight = getPath(root.right);
        maxPath=Math.max(maxPath,leftHeight+rightHeight);
        return Math.max(leftHeight,rightHeight) + 1 ;
    }

    /**NO.41  二叉树的层序遍历
     *      给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     * @param root
     * @return
     * 解法一：广度优先算法(BFS)
     *解法二：深度优先算法(DFS)
     *
     */
    @Override
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size=queue.size();
            List<Integer> tmpList = new ArrayList<>();
            while (size>0){
                TreeNode node = queue.poll();
                tmpList.add(node.val);
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
                size--;
            }
            list.add(tmpList);
        }
        return list;
    }

    /**NO.42  将有序数组转换为二叉树
     *
     *      给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
     * 平衡
     *  二叉搜索树。
     * @param nums
     * @return
     * 解法一：中序遍历(DFS)
     * 解法二：分治法
     *
     */
    @Override
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length==0) {
            return null;
        }
        int mid =  nums.length/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(Arrays.copyOfRange(nums,0,mid));
        root.right=sortedArrayToBST(Arrays.copyOfRange(nums,mid+1,nums.length));
        return root;
    }

    /**NO.43  验证二叉树搜索树
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     *
     * 有效 二叉搜索树定义如下：
     *
     * 节点的左
     * 子树
     * 只包含 小于 当前节点的数。
     * 节点的右子树只包含 大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     *
     * @param root
     * @return
     *
     * 解法一：深度优先算法(DFS)
     * 解法二：广度优先算法(BFS)
     *
     *
     */
    @Override
    public boolean isValidBST(TreeNode root) {
        if (root == null){
            return false;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        double minValue = -Double.MAX_VALUE;
        while (!stack.isEmpty()||curr!=null){
            if(curr!=null){
                stack.push(curr);
                curr =curr.left;
            }else{
                curr = stack.pop();
                if(curr.val<=minValue){
                    return false;
                }
                minValue = curr.val;
                curr = curr.right;
            }
        }
        return true;
    }

    /**
     * NO.43  二叉树搜索第k小的元素
     * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
     * @param root
     * @param k
     * @return
     * 解法一：中序遍历+栈
     * 解法二：记录子树的结点数
     * 解法三:平衡二叉搜索树
     * 解法四：中序遍历+排序
     * 解法五：中序遍历+优先队列
     *
     */
    @Override
    public int kthSmallest(TreeNode root, int k) {
        if(root==null){
            return 0;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty()||curr!=null){
            if(curr!=null){
                stack.push(curr);
                curr =curr.left;
            }else{
                curr = stack.pop();
                --k;
                if(k==0){
                    break;
                }
                curr = curr.right;
            }
        }

        return curr.val;
    }

    /** NO.44  二叉树右视图
     * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     * @param root
     * @return
     * 解法一：深度优先算法(DFS)
     * 解法二：广度优先算法(BFS)
     */
    @Override
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null){
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size=queue.size();
            while (size>0){
                TreeNode node = queue.poll();
                if(size==1){
                    list.add(node.val);
                }
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
                size--;

            }
        }
        return list;
    }

    /**NO.45  二叉树展开为列表
     * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
     *
     * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
     * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
     * @param root
     * 解法一：深度优先算法(DFS)
     * 解法二：广度优先算法(BFS)
     * 解法三：寻找前驱节点
     *
     */

    @Override
    public void flatten(TreeNode root) {
        if(root==null){
            return ;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty()||curr!=null){
            if(curr!=null){
                stack.push(curr);
                curr =curr.left;
            }else{
                curr = stack.pop();
                TreeNode tmp = curr.right;
                curr.right=curr.left;
                curr.left=null;
                while (curr.right!=null){
                    curr = curr.right;
                }
                curr.right =tmp;
                curr=tmp;

            }
        }

    }

    /**NO.46  从前序与中序遍历序列构造二叉树
     * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     * @param preorder
     * @param inorder
     * @return
     * 解法一：递归
     * 解法二：迭代
     * 解法三：分治
     *
     *
     */
    @Override
    public TreeNode buildTree(int[] preorder, int[] inorder) {
         if(preorder.length==0&&inorder.length==0){
             return null;
         }
         int preorderIndex=0;
         int inorderIndex=0;
         TreeNode root = new TreeNode(preorder[preorderIndex++]);
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
         while (preorderIndex<preorder.length&&inorderIndex<inorder.length){
               TreeNode tmp = stack.peek();
               if(inorder[inorderIndex]!=tmp.val){
                   tmp.left = new TreeNode(preorder[preorderIndex]);
                   stack.push(tmp.left);
               }else{
                   while (!stack.isEmpty()&&inorder[inorderIndex]==stack.peek().val){
                       tmp = stack.pop();
                       inorderIndex++;
                   }
                   tmp.right = new TreeNode(preorder[preorderIndex]);
                   stack.push( tmp.right);
               }
             preorderIndex++;
         }
        return root;
    }

    /**
     * NO.47  路径总和 III*
     * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
     *
     * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
     * @param root
     * @param targetSum
     * @return
     * 解法一：深度优先搜索
     * 解法一：前缀和
     *
     *
     */
    @Override
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null){
            return 0;
        }
        return pathSum(root.left, targetSum) + pathSum(root.right, targetSum)+ rootPathSum(root, Long.valueOf(targetSum));
    }

    public int rootPathSum(TreeNode root, Long targetSum) {
        if(root==null){
            return 0;
        }
         targetSum-= root.val;
        return(targetSum == 0 ? 1 : 0) + rootPathSum(root.left, targetSum) + rootPathSum(root.right, targetSum);
    }

    /**NO.48  二叉树的最近公共祖先
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     *
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     * @param root
     * @param p
     * @param q
     * @return
     * 解法一：递归
     * 解法二:存储父节点
     *
     */
    @Override
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 1. 先看根节点是不是祖先
        if(root==null || root==p || root==q){
            return root;
        }

        // 2. 如果根节点是祖先，有没有更近的祖先呢
        // 看看左子树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 看看右子树
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 3. 如果有的话显然只会在一侧 判断一下
        if(left==null){
            return right;
        }
        if(right==null){
            return left;
        }

        // 4. 如果没有更近的，默认还是返回root
        return root;
    }

    /**NO.49  二叉树中的最大路径和 *
     * 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
     *
     * 路径和 是路径中各节点值的总和。
     *
     * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
     * @param root
     * @return
     * 解法一：递归
     * 解法二：树形 DP(动态规划)
     *
     *
     */
    int maxPathSum=0;
    @Override
    public int maxPathSum(TreeNode root) {
        maxPathSum = root.val;
        getMaxPath(root);
        return maxPathSum;
    }

    private int getMaxPath(TreeNode root){
        if(root == null) {
            return 0;
        }
        int leftHeight =  Math.max(getMaxPath(root.left),0);
        int rightHeight = Math.max(getMaxPath(root.right),0);
        int maxPath = Math.max(leftHeight,rightHeight)+root.val;
        maxPathSum=Math.max(maxPathSum,leftHeight+rightHeight+root.val);
        return maxPath ;
    }



    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        Map<Character,Integer> map = new HashMap<>();
        for(char c :str.toCharArray()){
            map.put(c,map.getOrDefault(c,0)+1);
        }
        int count= map.keySet().toArray().length;
        System.out.println(count);
    }
}
